package com.LeeCode;

/**
 * 至少有 K 个重复字符的最长子串
 */

public class Code395 {
    public static void main(String[] args) {
        String s = "ababbc";
        int k = 2;
        System.out.println(new Code395().longestSubstring(s, k));
    }

    public int longestSubstring(String s, int k) {
        int n = s.length();
        if (n < k) return 0;
        int ans = 0;
        char[] chars = s.toCharArray();

        for (int level = 1; level <= 26; level++) {
            int[] cnt = new int[26];
            int left = 0, count = 0, kNum = 0;
            for (int right = 0; right < n; right++) {
                int index = chars[right] - 'a';
                cnt[index]++;
                if (cnt[index] == 1) {
                    count++;
                }
                if (cnt[index] == k) {
                    kNum++;
                }
                while (count > level) {
                    index = chars[left] - 'a';
                    cnt[index]--;
                    if (cnt[index] == 0) {
                        count--;
                    }
                    if (cnt[index] == k - 1) {
                        kNum--;
                    }
                    left++;
                }
                if (count == kNum) {
                    ans = Math.max(ans, right - left + 1);
                }
            }
        }

        return ans;
    }

}
